﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CS3Ex
{
    class Program
    {
        static IEnumerable<List<int>> QueensLINQ(int max) { return QueensLINQ(max, max); }

        static IEnumerable<List<int>> QueensLINQ(int n, int max)
        {
            return n == 0 
                    ?
                    new List<List<int>> {new List<int>()}
                    :
                    from b in QueensLINQ(n - 1, max)
                    from q in Enumerable.Range(0, max)
                    where Enumerable.Range(0, b.Count()).All(i => !(q == b[i] || Math.Abs(q - b[i]) == i + 1))
                    select new List<int>(new List<int> { q }.Concat(b));
        }

        static List<List<int>> Queens(int max) { return Queens(max, max); }

        static List<List<int>> Queens(int cur, int max)
        {
            var bs = new List<List<int>>();

            if (cur == 1)
            {
                for (int q = 0; q < max; q++)
                {
                    bs.Add(new List<int>(1) { q });
                }
            }
            else
            {
                foreach (var b in Queens(cur - 1, max))
                {
                    for (int q = 0; q < max; q++)
                    {
                        bool allOk = true;
                        for (int i = 0; i < b.Count(); i++)
                        {
                            if (q == b[i] || Math.Abs(q - b[i]) == i + 1)
                            {
                                allOk = false;
                                break;
                            }
                        }
                        if (allOk)
                        {
                            var newElem = new List<int>(cur) { q };
                            newElem.AddRange(b);
                            bs.Add(newElem);
                        }
                    }
                }
            }
            return bs;
        }

        public static IEnumerable<int> PrimesLINQ(IEnumerable<int> list) { return PrimesLINQ(list.FirstOrDefault(), new List<int>(list.Skip(1))); }

        public static IEnumerable<int> PrimesLINQ(int n, List<int> ns)
        {
            if(ns.Count == 0)
                return new List<int>(n);
            return new List<int> { n }.Concat(PrimesLINQ(from v in ns where v % n != 0 select v));
        }

        public static IEnumerable<int> Primes(IEnumerable<int> list) { return Primes(list.FirstOrDefault(), new List<int>(list.Skip(1))); }

        public static IEnumerable<int> Primes(int n, List<int> ns)
        {
            if (ns.Count == 0)
                return new List<int>(n);
            List<int> l = new List<int>();
            foreach (var v in ns)
            {
                if (v % n != 0)
                {
                    l.Add(v);
                }
            }
            return new List<int> { n }.Concat(PrimesLINQ(l));
        }

        static void Measure(Action f)
        {
            DateTime start = DateTime.Now;
            f();
            Console.WriteLine(DateTime.Now - start);
        }

        public static IEnumerable<int> PrimesNAT(int n)
        {
            List<int> result = new List<int>();
            int[] numbers = new int[n];
            for (int f = 0; f < n; f++) numbers[f] = 1;

            int i = 2;
            while (i < n)
            {
                result.Add(i);
                for (int j = i; j < n; j += i) numbers[j] = 0;

                while (i < n && numbers[i] == 0) i++;
            }

            return result;
        }

        static void Main(string[] args)
        {
            QueensLINQ(6).ToList().ForEach(l => { l.ForEach(le => Console.Write(le)); Console.WriteLine(); });

            Measure(() =>
            QueensLINQ(12).Count());

            Queens(6).ForEach(l => { l.ForEach(le => Console.Write(le)); Console.WriteLine(); });
            Measure(() =>
            Queens(12).Count());

            PrimesLINQ(Enumerable.Range(2, 200)).ToList().ForEach(v => Console.Write(v)); Console.WriteLine();

            Measure(() =>
                {
                    Console.WriteLine(PrimesLINQ(Enumerable.Range(2, 20000 - 2)).Count());
                    Console.WriteLine(PrimesLINQ(Enumerable.Range(2, 20000 - 2)).Count());
                    Console.WriteLine(PrimesLINQ(Enumerable.Range(2, 20000 - 2)).Count());
                    Console.WriteLine(PrimesLINQ(Enumerable.Range(2, 20000 - 2)).Count());
                    Console.WriteLine(PrimesLINQ(Enumerable.Range(2, 20000 - 2)).Count());
                }
            );

            PrimesNAT(200).ToList().ForEach(v => Console.Write(v)); Console.WriteLine();

            Measure(() =>
            {
                Console.WriteLine(Primes(Enumerable.Range(2, 20000 - 2)).Count());
                Console.WriteLine(Primes(Enumerable.Range(2, 20000 - 2)).Count());
                Console.WriteLine(Primes(Enumerable.Range(2, 20000 - 2)).Count());
                Console.WriteLine(Primes(Enumerable.Range(2, 20000 - 2)).Count());
                Console.WriteLine(Primes(Enumerable.Range(2, 20000 - 2)).Count());
            }
            );
        }
    }
}
